package chapter03;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LevelOrder102 {
    /**
     * 利用队列层序遍历
     * 首先将根节点放入队列 假设出队列的节点为x 处理x 如果左右子树不为空再将x左子树和x右子树加入队列 循环直到队列为空
     * process(queue) 处理queue中节点 queue中节点在同一层
     * 递归出口
     *  1).队列为空时 直接返回
     *     queue.isEmpty()==true
     *  2).遍历queue 取出节点并处理该节点 再将该节点左右子树加入队列work 将处理的结果加入res 递归work
     *     while !queue.isEmpty()
     *          cur=queue.poll()
     *          path.add(cur.val)
     *          if cur.left!=null -> work.add(cur.left)
     *          if cur.right!=null -> work.add(cur.right)
     *     res.add(path)
     *     process(work)
     */
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
   }

    List<List<Integer>> res;
    public List<List<Integer>> levelOrder(TreeNode root) {
        res=new LinkedList<>();
        if(root==null){
            return res;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        process(queue);
        return res;
    }

    public void process(Queue<TreeNode> queue){
        if(queue.isEmpty()){
            return;
        }
        Queue<TreeNode> work=new LinkedList<>();
        List<Integer> path=new LinkedList<>();
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            path.add(cur.val);
            if(cur.left!=null){
                work.add(cur.left);
            }
            if(cur.right!=null){
                work.add(cur.right);
            }
        }
        res.add(path);
        process(work);
    }
}
